GATE CSE 2003
Q21.
In a heap with n elements with the smallest element at the root, the 7^{th} smallest element ban be found in timeQ22.
A data structure is required for storing a set of integers such that each of the following operations can be done in O(logn) time, where n is the number of elements in the set. 1. Delection of the smallest element. 2. Insertion of an element if it is not already present in the set. Which of the following data structures can be used for this purpose ?Q23.
Consider the ALU shown below If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C0 only (+ and - denote addition and subtraction respectively)?Q24.
Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier isQ25.
Consider the following circuit composed of XOR gates and non-inverting buffers The non-inverting buffers have delays \delta _{1}= 2ns and \delta _{2}= 4ns as shown in the figure. Both XOR gates and al wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0. If the following waveform is applied at input. A, how many transition (s) (change of logic levels) occur (s) at B during the interval from 0 to 10 ns?Q26.
Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL) || ((P->data <= p->next->data) && f(p->next))); } For a given linked list p, the function f returns 1 if and only ifQ27.
Consider the following C function. float f(float x, int y) { float p, s; int i; for (s=1, p=1, i=1; i < y; i ++) { p*= x/i; s+=p; } return s; } For large values of y, the return value of the function f best approximatesQ29.
Consider the following functional dependencise in a database: Data_of_Birth \rightarrow Age Age \rightarrow Eligibility Name \rightarrow Roll_number Roll_number \rightarrow Name Course_number \rightarrow Course_name Course_number \rightarrow Instructor (Roll_number, Course_number) \rightarrow Grade The relation (Roll_number,Name,Date_of_brith,Age) isQ30.
A piecewise linear function f (x) is plotted using thick solid lines in the figure below (the plot is drawn to scale). If we use the Newton-Raphson method to find the roots of f(x) = 0 using x0, x1 and x2 respectively as initial guesses, the roots obtained would be